﻿using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Grafos;

namespace GrafosTestUnit {
    /// <summary>
    /// Testes nas classes Árvore e ÁrvorePonderada
    /// </summary>
    [TestClass]
    public class TesteÁrvore {

        /// <summary>
        /// Tenta criar uma árvore com loop, espera-se um erro
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria um vértice V1
        /// Cria uma árvore A
        /// Adiciona V1 a A
        /// Tenta adicionar (V1, V1) a A, causando uma ArgumentException
        /// </remarks>
        [TestMethod]
        [ExpectedException(typeof(ArgumentException))]
        public void ÁrvoreComLoop() {
            Vértice v1;
            Árvore a;

            v1 = new Vértice("Arv1");
            a = new Árvore();
            a.AdicionarVértice(v1);
            a.AdicionarAresta(v1, v1);
        }

        /// <summary>
        /// Tenta criar uma árvore com ciclo, espera-se um erro
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria três vértices V1, V2, V3
        /// Cria uma árvore A
        /// Ativa o ModoSeguro de A
        /// Adiciona os três vértices a A
        /// Adiciona (V1, V2) a A
        /// Adiciona (V2, V3) a A
        /// Tenta adicionar (V1, V3) a A, criando um ciclo e causando uma ArgumentException
        /// </remarks>
        [TestMethod]
        [ExpectedException(typeof(ArgumentException))]
        public void ÁrvoreComCiclo() {
            Vértice v1, v2, v3;
            Árvore a;

            v1 = new Vértice("Arv2");
            v2 = new Vértice("Arv3");
            v3 = new Vértice("Arv4");

            a = new Árvore();
            a.ModoSeguro = true;
            a.AdicionarVértice(v1);
            a.AdicionarVértice(v2);
            a.AdicionarVértice(v3);
            a.AdicionarAresta(v1, v2);
            a.AdicionarAresta(v2, v3);
            a.AdicionarAresta(v1, v3); // causa exceção
        }

        /// <summary>
        /// Tenta criar uma árvore ponderada com loop, espera-se erro
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria um vértice V1
        /// Cria uma árvore ponderada A
        /// Tenta adicionar (V1, V1) a A, causando uma ArgumentException
        /// </remarks>
        [TestMethod]
        [ExpectedException(typeof(ArgumentException))]
        public void ÁrvorePonderadaComLoop() {
            Vértice v1;
            ÁrvorePonderada a;

            v1 = new Vértice("Arv5");
            a = new ÁrvorePonderada();
            a.AdicionarVértice(v1);
            a.AdicionarAresta(v1, v1);
        }

        /// <summary>
        /// Tenta criar uma árvore ponderada com ciclo, espera-se erro
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria três vértices V1, V2 e V3
        /// Cria uma árvore ponderada A
        /// Adiciona os três vértices a A
        /// Adiciona (V1, V2) a A
        /// Adiciona (V2, V3) a A
        /// Tenta adicionar (V1, V3) a A, criando um ciclo e causando uma ArgumentException
        /// </remarks>
        [TestMethod]
        [ExpectedException(typeof(ArgumentException))]
        public void ÁrvorePonderadaComCiclo() {
            Vértice v1, v2, v3;
            ÁrvorePonderada a;

            v1 = new Vértice("Arv6");
            v2 = new Vértice("Arv7");
            v3 = new Vértice("Arv8");
            a = new ÁrvorePonderada();
            a.AdicionarVértice(v1);
            a.AdicionarVértice(v2);
            a.AdicionarVértice(v3);
            a.AdicionarAresta(v1, v2);
            a.AdicionarAresta(v2, v3);
            a.AdicionarAresta(v1, v3);
        }

        /// <summary>
        /// Cria uma árvore a partir de uma lista de predecessores
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria os vértices A..D
        /// Definem-se os predecessores:
        /// B->A
        /// C->A
        /// D->C
        /// Gera uma árvore A destes 4 vértices
        /// Verifica-se:
        /// A possui as arestas (A-B), (A-C), (C-D)
        /// A não possui ciclos
        /// A não possui as arestas (A-D), (B-C) nem (B-D)
        /// </remarks>
        [TestMethod]
        public void DePredec() {
            Vértice v1, v2, v3, v4;
            Árvore a;

            v1 = new Vértice("A");
            v2 = new Vértice("B");
            v3 = new Vértice("C");
            v4 = new Vértice("D");

            v2.Pi = v1;
            v3.Pi = v1;
            v4.Pi = v3;

            a = Árvore.GerarDePredecessores(new Vértice[] { v1, v2, v3, v4 }, true);

            v1 = a.BuscarVértice("A");
            v2 = a.BuscarVértice("B");
            v3 = a.BuscarVértice("C");
            v4 = a.BuscarVértice("D");

            Assert.IsTrue(a.PossuiArestaParalela(v1, v2));
            Assert.IsTrue(a.PossuiArestaParalela(v1, v3));
            Assert.IsTrue(a.PossuiArestaParalela(v3, v4));

            Assert.IsFalse(a.PossuiCiclo());
            Assert.IsFalse(a.PossuiArestaParalela(v1, v4));
            Assert.IsFalse(a.PossuiArestaParalela(v2, v3));
            Assert.IsFalse(a.PossuiArestaParalela(v2, v4));
        }

        /// <summary>
        /// Cria uma árvore ponderada a partir de uma lista de predecessores
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria os vértices A..D
        /// Define-se os predecessores e valores:
        /// B->A (2)
        /// C->A (5)
        /// D->C (8)
        /// Gera uma árvore A destes 4 vértices
        /// Verifica-se:
        /// A possui as arestas (A-B), (A-C), (C-D)
        /// A não possui ciclo
        /// A não possui as arestas (A-D), (B-C) nem (B-D)
        /// Os valores de peso das arestas são:
        /// A: raíz
        /// A-B: 2
        /// A-C: 5
        /// C-D: 3
        /// </remarks>
        [TestMethod]
        public void PonderadaDePredec() {
            Vértice v1, v2, v3, v4;
            ÁrvorePonderada a;

            v1 = new Vértice("A");
            v2 = new Vértice("B");
            v3 = new Vértice("C");
            v4 = new Vértice("D");

            v1.Lambda = 0;
            v2.Pi = v1;
            v2.Lambda = 2;
            v3.Pi = v1;
            v3.Lambda = 5;
            v4.Pi = v3;
            v4.Lambda = 8;

            a = ÁrvorePonderada.GerarDePredecessores(new Vértice[] { v1, v2, v3, v4 }, true);

            v1 = a.BuscarVértice("A");
            v2 = a.BuscarVértice("B");
            v3 = a.BuscarVértice("C");
            v4 = a.BuscarVértice("D");

            Assert.IsTrue(a.PossuiArestaParalela(v1, v2));
            Assert.IsTrue(a.PossuiArestaParalela(v1, v3));
            Assert.IsTrue(a.PossuiArestaParalela(v3, v4));

            Assert.IsFalse(a.PossuiCiclo());
            Assert.IsFalse(a.PossuiArestaParalela(v1, v4));
            Assert.IsFalse(a.PossuiArestaParalela(v2, v3));
            Assert.IsFalse(a.PossuiArestaParalela(v2, v4));

            Assert.AreEqual(2, ((ArestaPonderada)v1.ProcurarAresta(v2)).Valor);
            Assert.AreEqual(5, ((ArestaPonderada)v1.ProcurarAresta(v3)).Valor);
            Assert.AreEqual(3, ((ArestaPonderada)v3.ProcurarAresta(v4)).Valor);
        }

        /// <summary>
        /// Cria uma árvore ponderada a partir de predecessores, com múltiplas raízes
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria 5 vértices V1..V5
        /// Definem-se os predecessores e valores:
        /// V1: raíz
        /// V2-V1: 2
        /// V3-V2: 5
        /// V4: raíz
        /// V5-V4: 4
        /// Gera uma árvore A destes 5 vértices
        /// Verifica-se:
        /// A possui as arestas V1-V2, V2-V3 e V4-V5
        /// A possui 3 arestas e 5 vértices
        /// Os valores de peso das arestas são:
        /// V1-V2: 2
        /// V2-V3: 3
        /// V4-V5: 4
        /// </remarks>
        [TestMethod]
        public void PonderadaDePredecComMúltiplasRaízes() {
            ÁrvorePonderada a;
            Vértice[] v;
            
            v = Vértice.CriarConjuntoVértices("V", 5); // V1-V5

            v[0].Pi = null; // V1 é raíz
            v[0].Lambda = 0;
            v[1].Pi = v[0]; // V1-V2 (2)
            v[1].Lambda = 2;
            v[2].Pi = v[1]; // V2-V3 (3)
            v[2].Lambda = 5;
            v[3].Pi = null; // V4 é raíz
            v[3].Lambda = 0;
            v[4].Pi = v[3]; // V4-V5 (4)
            v[4].Lambda = 4;

            a = ÁrvorePonderada.GerarDePredecessores(v, true);

            Assert.IsTrue(a.PossuiArestaParalela("V1", "V2"));
            Assert.IsTrue(a.PossuiArestaParalela("V2", "V3"));
            Assert.IsTrue(a.PossuiArestaParalela("V4", "V5"));
            Assert.AreEqual(3, a.QuantidadeArestas);
            Assert.AreEqual(5, a.QuantidadeVértices);

            Assert.AreEqual(2, ((ArestaPonderada)a.BuscarVértice("V1").ProcurarAresta(a.BuscarVértice("V2"))).Valor);
            Assert.AreEqual(3, ((ArestaPonderada)a.BuscarVértice("V2").ProcurarAresta(a.BuscarVértice("V3"))).Valor);
            Assert.AreEqual(4, ((ArestaPonderada)a.BuscarVértice("V4").ProcurarAresta(a.BuscarVértice("V5"))).Valor);
        }

        /// <summary>
        /// Testa a criação do código de Prüfer
        /// </summary>
        /// <remarks>
        /// Processo:
        /// Cria os vértices A..H
        /// Cria uma árvore com as seguintes arestas:
        /// A-B, A-C, A-D, C-E, B-F, C-G, E-H
        /// Compara-se todos os elementos do código de Prüfer gerado com o seguinte gabarito:
        /// {A, B, A, C, C, E}
        /// </remarks>
        [TestMethod]
        public void CriarPrüfer() {
            Árvore a;
            string[] resposta;
            string[] gabarito;
            int i;
            
            gabarito = new string[] { "A", "B", "A", "C", "C", "E" };
            
            a = new Árvore();
            a.AdicionarVértice("A", "B", "C", "D", "E", "F", "G", "H");
            a.AdicionarAresta("A", "B");
            a.AdicionarAresta("A", "C");
            a.AdicionarAresta("A", "D");
            a.AdicionarAresta("C", "E");
            a.AdicionarAresta("B", "F");
            a.AdicionarAresta("C", "G");
            a.AdicionarAresta("E", "H");

            resposta = a.CódigoDePrüfer();

            for (i = 0; i < gabarito.Length; i++) {
                Assert.AreEqual(gabarito[i], resposta[i]);
            }

        }
    }
}
